package aufgabe1;

public class EditDistance {
	int[][] matrix;
	char[] u,v;

	protected int ed(int i, int j) {
		if (matrix[i][j] != -1) {
		}
		// in case i == 0 && j == 0 : matrix[i][j] is set to 0 here
		else if (i == 0) {
			matrix[i][j] = j;
		}
		else if (j == 0) {
			matrix[i][j] = i;
		}
		else if (u[i-1] == v[j-1]) {
			matrix[i][j] = ed(i-1, j-1);
		}
		else {
			int iMinus1j       = ed(i-1, j);
			int iMinus1jMinus1 = ed(i-1, j-1);

			matrix[i][j] = (iMinus1j < iMinus1jMinus1) ? 1 + iMinus1j : 1 + Math.min(ed(i, j-1), iMinus1jMinus1);
		}

		return matrix[i][j];
	}

	/**
	 * Calculates the edit-distance, also called Levenshtein-distance, of the given strings.
	 *
	 * @param one
	 * @param two
	 *
	 * @return
	 */
	public int editDistance(String one, String two) {
		u = one.toCharArray();
		v = two.toCharArray();

		int m = one.length();
		int n = two.length();

		matrix = new int[m+1][n+1];

		initMatrix();

		return ed(m, n);
	}

	protected void initMatrix() {
		for(int i = 0; i < matrix.length; i++) {
			for(int j = 0; j < matrix[0].length; j++) {
				matrix[i][j] = -1;
			}
		}
	}

	/**
	 * Prints the edit-distance matrix to console.
	 */
	public void printMatrix() {
		System.out.println("\nMatrix:");

		int dpEntries   = 0;
		int lazyEntries = 0;

		for(int i = 0; i < matrix.length; i++) {
			for(int j = 0; j < matrix[0].length; j++) {
				dpEntries++;

				if (matrix[i][j] != -1) lazyEntries++;

				System.out.print(matrix[i][j]+"\t");
			}
			System.out.print("\n");
		}

		System.out.println("\nMatrixeinträge nach DP: "+dpEntries+" , mit lazy-Methode: "+lazyEntries);

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		EditDistance ed = new EditDistance();

//		String u = "";
//		String v = "";

//		String u = "aabaa";
//		String v = "aaaba";

//		String u = "bcacd";
//		String v = "dbadad";

		String u = "ZEITGEIST";
		String v = "FREIZEIT";

//		String u = "meilenstein";
//		String v = "levenshtein";

//		String u = "Ein ganz langer Satz";
//		String v = "Eig ganz langer Sats";

//		String u = "Ein ganz langer Satz";
//		String v = "Komplett unterschiedlicher Satz hier";

//		String u = "Ein ganz langer Satz steht hier in dieser Zeile drin";
//		String v = "Ein ganz langer Satz steht hier in dieser Spalte drin";

//		String u = "acgtgagtatagatagatgccccagagggttagacagatagaccgatgagacgagtagacggagtttagagagatgatgc";
//		String v = "acgtgattatagatagatgccccagagcgttagacagataaaccgatgagacgtgtagacggagttcagagagatgatgc";

//		String u = "acgtgagtatagatagatgccccagagggttagacagatagaccgatgagacgagtagacggagtttagagagatgatgcacgtgagtatagatagatgccccagagggttagacagatagaccgatgagacgagtagacggagtttagagagatgatgc";
//		String v = "acgtgattatagatagatgccccagagcgttagacagataaaccgatgagacgtgtagacggagttcagagagatgatgcacgtgattatagatagatgccccagagcgttagacagataaaccgatgagacgtgtagacggagttcagagagatgatgc";

		long timeBefore = System.nanoTime();

		int result = ed.editDistance(u, v);

		long timeAfter = System.nanoTime();

		ed.printMatrix();

		System.out.println("Edit-Distance of \""+u+"\" and \""+v+"\" is: "+result);

		System.out.println("\nExecution time: "+(timeAfter-timeBefore)/1000. +" microseconds");
	}

}
